package internal.database;

/*******************************************************************************
 * @file LinHash.java
 *
 * @author  John Miller
 */

import java.io.*;
import java.lang.reflect.Array;

import static java.lang.System.out;

import java.util.*;

/*******************************************************************************
 * This class provides hash maps that use the Linear Hashing algorithm. A hash
 * table is created that is an array of buckets.
 */
@SuppressWarnings("all")
public class LinHash<K, V> extends AbstractMap<K, V> implements Serializable,
		Cloneable, Map<K, V> {
	/**
	 * The number of slots (for key-value pairs) per bucket.
	 */
	private static final int SLOTS = 4;

	/**
	 * The class for type K.
	 */
	private final Class<K> classK;

	/**
	 * The class for type V.
	 */
	private final Class<V> classV;

	/***************************************************************************
	 * This inner class defines buckets that are stored in the hash table.
	 */
	private class Bucket {
		int nKeys;
		K[] key;
		V[] value;
		Bucket next;

		@SuppressWarnings("unchecked")
		Bucket(Bucket n) {
			nKeys = 0;
			key = (K[]) Array.newInstance(classK, SLOTS);
			value = (V[]) Array.newInstance(classV, SLOTS);
			next = n;
		} // constructor
	} // Bucket inner class

	/**
	 * The list of buckets making up the hash table.
	 */
	private final List<Bucket> hTable;

	/**
	 * The modulus for low resolution hashing
	 */
	private int mod1;

	/**
	 * The modulus for high resolution hashing
	 */
	private int mod2;

	/**
	 * Counter for the number buckets accessed (for performance testing).
	 */
	private int count = 0;

	/**
	 * The index of the next bucket to split.
	 */
	private int split = 0;

	/***************************************************************************
	 * Construct a hash table that uses Linear Hashing.
	 * 
	 * @param classK
	 *            the class for keys (K)
	 * @param classV
	 *            the class for keys (V)
	 * @param initSize
	 *            the initial number of home buckets (a power of 2, e.g., 4)
	 */
	public LinHash(Class<K> _classK, Class<V> _classV, int initSize) {
		classK = _classK;
		classV = _classV;
		hTable = new ArrayList<>();
		mod1 = initSize;
		mod2 = 2 * mod1;
	} // LinHash

	/***************************************************************************
	 * Return a set containing all the entries as pairs of keys and values.
	 * 
	 * @return the set view of the map
	 */
	public Set<Map.Entry<K, V>> entrySet() {
		Set<Map.Entry<K, V>> enSet = new HashSet<>();

		// -----------------\\
		// TO BE IMPLEMENTED \\
		// ---------------------\\

		return enSet;
	} // entrySet

	/***************************************************************************
	 * Given the key, look up the value in the hash table.
	 * 
	 * @param key
	 *            the key used for look up
	 * @return the value associated with the key
	 */
	public V get(Object key) {
		int i = h(key);

		// -----------------\\
		// TO BE IMPLEMENTED \\
		// ---------------------\\

		return null;
	} // get

	/***************************************************************************
	 * Put the key-value pair in the hash table.
	 * 
	 * @param key
	 *            the key to insert
	 * @param value
	 *            the value to insert
	 * @return null (not the previous value)
	 */
	public V put(K key, V value) {
		int i = h(key);

		// -----------------\\
		// TO BE IMPLEMENTED \\
		// ---------------------\\

		return null;
	} // put

	/***************************************************************************
	 * Return the size (SLOTS * number of home buckets) of the hash table.
	 * 
	 * @return the size of the hash table
	 */
	public int size() {
		return SLOTS * (mod1 + split);
	} // size

	/***************************************************************************
	 * Print the hash table.
	 */
	private void print() {
		out.println("Hash Table (Linear Hashing)");
		out.println("-------------------------------------------");

		// -----------------\\
		// TO BE IMPLEMENTED \\
		// ---------------------\\

		out.println("-------------------------------------------");
	} // print

	/***************************************************************************
	 * Hash the key using the low resolution hash function.
	 * 
	 * @param key
	 *            the key to hash
	 * @return the location of the bucket chain containing the key-value pair
	 */
	private int h(Object key) {
		return key.hashCode() % mod1;
	} // h

	/***************************************************************************
	 * Hash the key using the high resolution hash function.
	 * 
	 * @param key
	 *            the key to hash
	 * @return the location of the bucket chain containing the key-value pair
	 */
	private int h2(Object key) {
		return key.hashCode() % mod2;
	} // h2

	/***************************************************************************
	 * The main method used for testing.
	 * 
	 * @param the
	 *            command-line arguments (args [0] gives number of keys to
	 *            insert)
	 */
	public static void main(String[] args) {
		LinHash<Integer, Integer> ht = new LinHash<>(Integer.class,
				Integer.class, 11);
		int nKeys = 30;
		if (args.length == 1)
			nKeys = Integer.valueOf(args[0]);
		for (int i = 1; i < nKeys; i += 2)
			ht.put(i, i * i);
		ht.print();
		for (int i = 0; i < nKeys; i++) {
			out.println("key = " + i + " value = " + ht.get(i));
		} // for
		out.println("-------------------------------------------");
		out.println("Average number of buckets accessed = " + ht.count
				/ (double) nKeys);
	} // main

} // LinHash class
